7405. Мороженое

Степан и его друзья поехали в отпуск в Ужляндию. Скрываясь от жары, они решили приобрести мороженого. Имеется n вкусов мороженого, пронумерованных от 1 до n. Поскольку некоторые вкусы несовместимы, такие пары следует избегать, иначе будет очень неприятный вкус. Степан хочет знать, сколько существует способов выбрать три разные вкусы мороженого так, чтобы среди них не было ни одной несовместимой пары. Порядок вкусов не в счет.

Вход. Первая строка содержит два неотрицательных целых числа n и m (1 ≤ n ≤ 200, 1 ≤ m ≤ 10000) – количество вкусов и количество несовместимых пар вкусов. Следующие m строк описывают пары несовместимых вкусов.

Выход. Выведите одно число – количество способов совершить выбор.

Пример входа	Пример выхода
5 3 1 2 3 4 1 3	3

РЕШЕНИЕ

цикл

Анализ алгоритма

В двумерном массиве mas запомним пары несовместимых вкусов: присвоим mas[i][j] = 1, если вкусы i и j несовместимы и mas[i][j] = 0 иначе.

В задаче следует найти количество троек разных вкусов. При помощи тройного цикла переберем тройки вкусов (i, j, k), где i < j < k. Для каждой пары из тройки (i, j), (i, k), (j, k) проверим, является ли она совместимой.

Пример

Для приведенного примера возможными тройками являются (1 4 5), (2 3 5) и (2 4 5). Матрица совместимости вкусов имеет вид:

Реализация алгоритма

Объявим массив mas для запоминания несовместимых пар.

#define MAX 201

int mas[MAX][MAX];

Читаем входные данные.

scanf("%d %d", &n, &m);

memset(mas, 0, sizeof(mas));

Читаем несовместимые пары, информацию о них запоминаем в массиве mas.

for (i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

mas[a][b] = mas[b][a] = 1;

}

Перебираем тройки вкусов (i, j, k) так что i < j < k. Для каждой пары из тройки проверяем, является ли она совместимой. Количество троек подсчиываем в переменной res.

res = 0;

for (i = 1; i <= n; i++)

for (j = i + 1; j <= n; j++)

for (k = j + 1; k <= n; k++)

if ((mas[i][j] == 0) && (mas[i][k] == 0) && (mas[j][k] == 0)) res++;

Выводим количество способов совершить выбор.

printf("%d\n", res);